package leetcode_300;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;


/**
 *@author 周杨
 *WordSearchII_212 回溯法搜索矩阵字符串
 *describe:AC 10%
 *2018年6月14日 下午7:20:56
 */
public class WordSearchII_212 {
	char [][] board;
	boolean [][]judge;
	String word;
	Map<Character,List<Integer>> map;
	public static void main(String[] args) {
		WordSearchII_212 test=new WordSearchII_212();
		char [][] board=new char[][] {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
		System.out.println(test.exist(board, "ABCCED"));
		System.out.println(test.exist(board, "SEE"));
		System.out.println(test.exist(board, "ABCB"));
		char[][] board1=new char[][] {{'a','a','a','a'},{'a','a','a','a'},{'a','a','a','a'}};
		System.out.println(test.exist(board1, "aaaaaaaaaaaaa"));
	}
	 public List<String> findWords(char[][] board, String[] words) {
	        List<String>res =new ArrayList<String>();
	        map=new HashMap<Character,List<Integer>>();
	        for(int i=0;i<board.length;++i)//构建字符地址map
	    		for(int j=0;j<board[0].length;++j) {
	    			List<Integer> list=map.get(board[i][j]);
	    			if(list==null) {//第一次出现
	    				list=new ArrayList<Integer>();
	    				list.add(i);
	    				list.add(j);
	    				map.put(board[i][j], list);
	    			}
	    			else {
	    				list.add(i);
	    				list.add(j);
	    			}
	    		}
	        for(String s:words)
	            if(exist(board,s)) {
	            	if(!res.contains(s))
	            		res.add(s);
	            }
	        return res;
	    }
	 
	 
    public boolean exist(char[][] board, String word) {
    	if(word.length()>board.length*board[0].length)
    		return false;
    	this.board=board;
    	this.word=word;
    	this.judge =new boolean[board.length][board[0].length];//用来判断哪些坐标是已经走过的
    	List<Integer> list=map.get(word.charAt(0));
    	if(list==null)
    		return false;
    	else {
    		boolean res=false;
    		for(int i=0;i<list.size();i+=2) {
    			res=help(list.get(i),list.get(i+1),0,0);//第一步已经校验
    			if(res)
    				return true;
    		}
    		return false;
    	}
    }
    
    public boolean help(int row,int col,int direction,int index) {//1 2 3 4 对应上下左右
    	if(row>=board.length||col>=board[0].length||col<0||row<0||index>=this.word.length())
    		return false;
    	if(this.word.charAt(index)!=board[row][col]) {//如果字符不匹配 直接返回false
    		return false;
    	}
    	else {//字符匹配
    		if(judge[row][col])
        		return false;
        	judge[row][col]=true;
    		if(index==this.word.length()-1){
    			return true;
    		}
    	}
    	boolean res=false;
    	if(direction!=2) {//上次走的下
    		res=help(row-1,col,1,index+1);
    	}
    	if(!res&&direction!=1)//上次走的上
    		res=help(row+1,col,2,index+1);
    	if(!res&&direction!=4)//上次走的右
    		res=help(row,col-1,3,index+1);
    	if(!res&&direction!=3)//上次走的左
    		res=help(row,col+1,4,index+1);
    	judge[row][col]=false;
    	return res;
    }

}
